package com.cg.leetcode;

import org.junit.Test;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 435.无重叠区间
 *
 * @author cg
 * @program LeetCode->LeetCode_435
 * @create 2022-09-08 14:53
 **/
public class LeetCode_435 {

    @Test
    public void test435() {
        System.out.println(eraseOverlapIntervals(new int[][]{{1, 2}, {2, 3}, {3, 4}, {1, 3}}));
        System.out.println(eraseOverlapIntervals(new int[][]{{1, 2}, {1, 2}, {1, 2}}));
        System.out.println(eraseOverlapIntervals(new int[][]{{1, 2}, {2, 3}}));
    }

    /**
     * 给定一个区间的集合 intervals，其中 intervals[i] = [start_i, end_i]。返回 需要移除区间的最小数量，使剩余区间互不重叠。
     * <p>
     * 示例 1:
     * 输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
     * 输出: 1
     * 解释: 移除 [1,3] 后，剩下的区间没有重叠。
     * <p>
     * 示例 2:
     * 输入: intervals = [ [1,2], [1,2], [1,2] ]
     * 输出: 2
     * 解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
     * <p>
     * 示例 3:
     * 输入: intervals = [ [1,2], [2,3] ]
     * 输出: 0
     * 解释: 你不需要移除任何区间，因为它们已经是无重叠的了。
     * <p>
     * 提示:
     * 1 <= intervals.length <= 10^5
     * intervals[i].length == 2
     * -5 * 10^4 <= start_i < end_i <= 5 * 10^4
     *
     * @param intervals
     * @return
     */
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, Comparator.comparingInt(o -> o[1]));
        // result记录非交叉区间的个数, edge记录区间分割点
        int result = 0, edge = Integer.MIN_VALUE;
        for (int i = 0; i < intervals.length; i++) {
            if (intervals[i][0] >= edge) {
                edge = intervals[i][1];
            } else {
                result++;
            }
        }
        return result;
    }

}
